/*************************************************************
* Strip Packing Problem
* 
*
* */

#include <algorithm>
#include <climits>

#include <set>

#include "dispersa.h"

Dispersa::Dispersa() {
}
         
Dispersa::~Dispersa() {
}

Dispersa::Dispersa(list<Rectangulo> lista_in, Contenedor C_) : Heuristica(lista_in) {
	C = C_;
}

list<Rectangulo> Dispersa::generaInicial() {
	return generaConjuntoSoluciones(2)[0].getLista();
}

list<Rectangulo> Dispersa::mejoraSolucion() {
	crearPoblacion();
	do {
		crearRefSet();
		do {
			crearSubSet();
			combinarSoluciones();
			mejorarSoluciones();
			actualizarRefSet();
		} while (paradaInterno());
	} while (paradaIntermedio());

	return refset[0].first.getLista();
}

bool Dispersa::paradaInterno() {
	//cout << "+ DISPERSA::paradaInterno" << endl;
	if (subset.size() > 0) {
		subset.clear();
		//cout << "- DISPERSA::paradaInterno -> TRUE" << endl;
		return true;
	}
	//cout << "- DISPERSA::paradaInterno -> FALSE" << endl;
	return false;
}

bool Dispersa::paradaIntermedio() {
	oldset.clear();
	//cout << "+ DISPERSA::paradaIntermedio" << endl;
	if (poblacion.size() >= N_REFSET) {
		refset.erase (refset.begin() + (N_REFSET - (N_REFSET / 2)), refset.end());
		//cout << "- DISPERSA::paradaIntermedio -> TRUE" << endl;
		return true;
	}
	//cout << "- DISPERSA::paradaIntermedio -> FALSE" << endl;
	return false;
}

void Dispersa::crearPoblacion() {
	//cout << "+ DISPERSA::crearPoblacion" << endl;

	// Limpiamos la informacion de la iteracion anterior
	poblacion.clear();
	refset.clear();

	// Creamos un conjunto de soluciones
	poblacion = generaConjuntoSoluciones(N_POBLACION);

	// Realizamos una mejora local
	for (int i = 0; i < poblacion.size(); i++) {
		poblacion[i] = busquedaLocal(poblacion[i]);
	}

	// Los ordenamos por altura
	sort(poblacion.begin(), poblacion.end());
	//cout << "- DISPERSA::crearPoblacion " << iteracion << endl;
}

void Dispersa::crearRefSet() {
	//cout << "+ DISPERSA::crearRefSet" << endl;

	// RefSet1 -> Soluciones de Mejor Altura
	// Si RefSet = Vacio -> Mejores de la poblacion
	if (refset.empty()) {		
		for (int i = 0; i < (N_REFSET - (N_REFSET / 2)); i++) {
			refset.push_back(pair <Solucion, bool>(poblacion[i], false));
		}
		//cout << "| DISPERSA::crearRefSet: R1" << endl;
	}
	// Si no mejores previamente obtenidas

	//cout << "| DISPERSA::crearRefSet: R2" << endl;
	// RefSet2 -> Soluciones más Dispersas
	for (int i = 0; i < (N_REFSET / 2); i++) {
		int maxDisperso = 0;
		int maxDispersion = distancia(refset[i].first, poblacion[maxDisperso]);

		for (int j = 1; j < poblacion.size(); j++) {
			int newDispersion = distancia(refset[i].first, poblacion[j]);

			// Los valores mas cercanos al cero son las soluciones mas dispersas
			if (maxDispersion > newDispersion) {
				maxDispersion = newDispersion;
				maxDisperso = j;
			}
		}
		
		refset.push_back(pair <Solucion, bool>(poblacion[maxDisperso], false));

		// Esto evita la re-insercción en el RefSet
		poblacion.erase(poblacion.begin() + maxDisperso);		
	}

	// RefSet = RefSet1 U RefSet2
	//cout << "- DISPERSA::crearRefSet T.Pob: " << poblacion.size() << " T.RefSet: " << refset.size() << endl;
}

void Dispersa::crearSubSet() {
	for (int i = 0; i < refset.size(); i++) {
		if (refset[i].second == false) {
			set <Solucion> sol;
			vector <pair <Solucion, bool> > cand = refset;

			cand.erase(cand.begin() + i);
			sol.insert(refset[i].first);

			recursiveSubSet(sol, cand, 1, N_SUBSET);

			refset[i].second == true;
		}
	}
}

void Dispersa::recursiveSubSet(set <Solucion>& tmp, vector <pair <Solucion, bool> >& cand, const int& level, const int& maxLevel) {
	if (level == maxLevel) {
		if (oldset.insert(tmp).second == false) {
			//cout << "Ya estaba" << endl; 
		}
		else {
			subset.insert(tmp);
		}
	}
	else {
		for (int i = 0; i < cand.size(); i++) {
			pair <Solucion, bool> aux = cand.back();
			cand.pop_back();
			tmp.insert(aux.first);

			recursiveSubSet(tmp, cand, level + 1, maxLevel);
		
			tmp.erase(aux.first);
			cand.insert(cand.begin(), aux);
		}
	}
}
	
void Dispersa::combinarSoluciones() {
	for (set <set <Solucion> > :: iterator i = subset.begin(); i != subset.end(); i++) {
		Solucion sol = *(i -> begin());
	
		int jPos = 0; 
		for (set <Solucion> :: iterator j = (i -> begin()); j != (i -> end()); j++) {
			Solucion comb = *j;
			sol = combinaSoluciones(sol, comb, jPos * (i -> size())/N_SUBSET, 0);

			jPos++;
		}

		combinacion.push_back(sol);
	}
	subset.clear();
}

void Dispersa::mejorarSoluciones() {
	for (int i = 0; i < combinacion.size(); i++) {
		combinacion[i] = busquedaLocal(combinacion[i]);
	}
}

int refSetMejorado;

void Dispersa::actualizarRefSet() {
	sort(refset.begin(), refset.end());

	for (int i = 0; i < combinacion.size(); i++) {
		if (combinacion[i].getValor() < refset[refset.size() - 1].first.getValor()) {
			refset[refset.size() - 1] = pair <Solucion, bool> (combinacion[i], false);
			sort(refset.begin(), refset.end());
		}
	}

	combinacion.clear();
}

// Se elimina la mejora local por el momento
Solucion Dispersa::busquedaLocal(Solucion sol) {
	sol.setValor(C.calcularAltura(sol.getLista()));
	return sol;
}


list <Rectangulo> Dispersa::branchBound(list <Rectangulo> init, list <Rectangulo> candidatos, int& minAltura) {
}

// 
// 1p - El rectangulo existe en la solucion
// 2p - Esta en la misma posicion / No esta en la misma posicion pero tiene el mismo giro
// 3p - Esta en la misma posicion y tiene el mismo giro
//
// Los valores mas cercanos a cero son las soluciones más dispersas.

// Esta función mide la similitud entre dos soluciones lo que implica
// que cuantos mas puntos tenga, mas similar es.

int Dispersa::distancia(Solucion a, Solucion b) {
	int dispersion = 0;
	
	vector <Rectangulo> lista(a.getLista().begin(), a.getLista().end());
	vector <Rectangulo> lista2(b.getLista().begin(), b.getLista().end());
	
	for (int i = 0; i < lista.size(); i++) {
		for (int j = 0; j < lista2.size(); j++) {
			if (lista[i].getid() == lista2[j].getid()) {
				dispersion++;

				if (i == j) {
					dispersion++;
				}
				if (lista[i].isRotado() == lista2[j].isRotado()) {
					dispersion++;
				}
			}
		}
	}

	return dispersion;
}
/*
int Dispersa::distancia(Solucion a, Solucion b) {
	int dispersion = 0;
	
	vector <Rectangulo> lista = a.getLista();
	vector <Rectangulo> lista2 = b.getLista();

	list <Rectangulo> :: iterator i;
	
	int iPos = 0;
	for (i = lista.begin(); i != lista.end(); i++) {
		list <Rectangulo> :: iterator j;	
		int jPos = 0;
		for (j = lista2.begin(); j != lista2.end(); j++) {
			if (i -> getid() == j -> getid()) {
				if (iPos == jPos) {
					dispersion++;
				}
				if (i -> isRotado() == j -> isRotado()) {
					dispersion++;
				}
			}
			
			jPos++;
		}

		iPos++;
	}

	return dispersion;
}
*/
